π§· μ΄μ§ νμ νΈλ¦¬
μ΄μ§ νμ + μ°κ²° 리μ€νΈ
- μ΄μ§ νμ : νμμ μμλλ μκ°λ³΅μ‘λλ , νμ§λ§ μ½μ , μμ κ° λΆκ°λ₯
- μ°κ²° 리μ€νΈ : μ½μ , μμ μ μκ°λ³΅μ‘λλ, νμνλ μκ°λ³΅μ‘λκ°
μ΄ λ κ°μ§λ₯Ό ν©νμ¬ μ₯μ μ λͺ¨λ μ»μ΄ ν¨μ¨μ μΈ νμ λ₯λ ₯κ³Ό μλ£μ μ½μ , μμ λ κ°λ₯νκ² νλ μ΄μ§ νμ νΈλ¦¬
πͺ νΉμ§
- λ Έλμ μ μ₯λ ν€λ μ μΌ (μ€λ³΅μ΄ μμ΄μΌ ν¨)
- κ° λ Έλμ μμμ΄ 2κ° μ΄ν
- κ° λ Έλμ μΌμͺ½ μμμ λΆλͺ¨λ³΄λ€ μκ³ , μ€λ₯Έμͺ½ μμμ λΆλͺ¨λ³΄λ€ νΌ
- μΌμͺ½κ³Ό μ€λ₯Έμͺ½ μλΈ νΈλ¦¬λ μ΄μ§ νμ νΈλ¦¬
μ€λ³΅μ΄ μμ΄μΌ νλ μ΄μ
: κ²μ λͺ©μ μλ£κ΅¬μ‘°μΈλ°, κ΅³μ΄ μ€λ³΅μ΄ λ§μ κ²½μ°μ νΈλ¦¬λ₯Ό μ¬μ©νμ¬ κ²μ μλλ₯Ό λλ¦¬κ² ν νμκ° μλ€.
μ΄μ§ νμ νΈλ¦¬μ μνλ "μ€μ μν(inorder)" λ°©μμΌλ‘, μ λ ¬λ μμλ‘ μ½μ μ μλ€.
πͺ BST ν΅μ¬ μ°μ°
- κ²μ
- μ½μ
- μμ
- νΈλ¦¬ μμ±, μμ
πͺ μκ° λ³΅μ‘λ
λ Έλ κ°μκ° Nκ°μΌ λ,
- κ· λ± νΈλ¦¬:
- νΈν₯ νΈλ¦¬:
μ½μ , κ²μ, μμ μκ°λ³΅μ‘λλ νΈλ¦¬μ Depthμ λΉλ‘
μμ μ 3κ°μ§ κ²½μ°
- μμμ΄ μλ 리ν λ ΈλμΌ λ -> κ·Έλ₯ μμ !
- μμμ΄ 1κ°μΈ λ ΈλμΌ λ -> μμ λ Έλμ κ΅ν ν, μμ
- μμμ΄ 2κ°μΈ λ ΈλμΌ λ -> μ€λ₯Έμͺ½ μμ λ Έλμμ κ°μ₯ μμ κ° λλ μΌμͺ½ μμ λ Έλμμ κ°μ₯ ν° κ°κ³Ό κ΅ν ν, μμ
νΈν₯λ νΈλ¦¬λ μκ°λ³΅μ‘λκ° μ΄λ―λ‘ νΈλ¦¬λ₯Ό μ¬μ©ν μ΄μ κ° μλ€!
- μ΄λ₯Ό λ°λ‘ μ‘λλ‘
Rebalancingνλ κ°μ λ°©μμ΄ AVL Tree, RedBlack Tree
class BinarySearchTree {
public class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public Node root;
public BinarySearchTree() {
this.root = null;
}
public boolean find(int id) {
Node cur = root;
while(cur != null) {
if (cur.data == id) return true;
else if(cur.data > id) cur = cur.left;
else cur = cur.right;
}
return false;
}
public boolean delete(int id) {
Node parent = root;
Node cur = root;
boolean isLeftChild = false;
while(cur.data != id) {
parent = cur;
if (cur.data > id) {
isLeftChild = true;
cur = cur.left;
} else {
isLeftChild = false;
cur = cur.right;
}
if (cur == null) return false;
}
// case1. μμ λ
Έλκ° μλ κ²½μ° -> κ·Έλ₯ μμ
if (cur.left == null && cur.right == null) {
if (cur == root) root = null;
if (isLeftChild == true) parent.left = null;
else parent.right = null;
}
// case2. μμ λ
Έλκ° 1κ°μΈ κ²½μ° -> κ΅ν ν μμ
else if (cur.right == null) {
if (cur == root) root = cur.left;
else if (isLeftChild) parent.left = cur.left;
else parent.right = cur.left;
} else if (cur.left == null) {
if (cur == root) root = cur.left;
else if (isLeftChild) parent.left = cur.right;
else parent.right = cur.right;
}
// case3. μμ λ
Έλκ° 2κ°μΈ κ²½μ° -> μ€λ₯Έμͺ½ μμ λ
Έλ μ€ μ΅μκ°κ³Ό κ΅ν ν μμ
else if (cur.left != null && cur.right != null) {
Node minNode = getMin(cur);
if (cur == root) root = minNode;
else if (isLeftChild) parent.left = minNode;
else parent.right = minNode;
minNode.left = cur.left;
}
return true;
}
// μ€λ₯Έμͺ½ μλΈ νΈλ¦¬μμ μ΅μκ°μ λ°ν
public Node getMin(Node deleteNode) {
Node minNode = null;
Node minNodeParent = null;
Node cur = deleleNode.right;
while(cur != null) {
minNodeParent = minNode;
minNode = cur;
cur = cur.left;
}
if (minNode != deleleNode.right) {
minNodeParent.left = minNode.right;
minNode.right = deleleNode.right;
}
return minNode;
}
public void insert(int id) {
Node newNode = new Ndoe(id);
if (root == null) {
root = newNode;
return;
}
Node cur = root;
Node parent = null;
while(true) {
parent = cur;
if (id < cur.date) {
cur = cur.left;
if (cur == null) {
parent.left = newNode;
return;
}
} else {
cur = cur.right;
if (cur == null) {
parent.right = newNode;
return;
}
}
}
}
public void print(Node root) {
if (root != null) {
print(root.left);
System.out.println(" " + root.date);
print(root.right);
}
}
}